0096. 不同的二叉搜索树【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划（卡特兰数）

1. 📝 题目描述

• leetcode

给你一个整数 n，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

---

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

---

提示：

• 1 <= n <= 19

2. 🎯 s.1 - 动态规划（卡特兰数）

c

int numTrees(int n) {
    int dp[n + 1];
    memset(dp, 0, sizeof(dp));
    dp[0] = 1; dp[1] = 1;
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= i; j++)
            dp[i] += dp[j - 1] * dp[i - j]; // 左子树 * 右子树
    return dp[n];
}

js

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function (n) {
  const dp = new Array(n + 1).fill(0)
  dp[0] = 1
  dp[1] = 1
  for (let i = 2; i <= n; i++)
    for (let j = 1; j <= i; j++) dp[i] += dp[j - 1] * dp[i - j] // 左子树 * 右子树
  return dp[n]
}

py

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = dp[1] = 1
        for i in range(2, n + 1):
            for j in range(1, i + 1):
                dp[i] += dp[j - 1] * dp[i - j]  # 左子树 * 右子树
        return dp[n]

• 时间复杂度：$O(n^2)$，双层循环填表
• 空间复杂度：$O(n)$，dp 数组的大小

算法思路：

• dp[i] 表示 i 个节点能组成的不同 BST 的数量，即卡特兰数 $C_n$
• 枚举每个节点 j 作为根，左子树有 j-1 个节点，右子树有 i-j 个节点
• 转移方程：$dp[i]=\sum _{j=1}^{i}dp[j-1]\times dp[i-j]$
• 初始化：$dp[0]=dp[1]=1$，空树和单节点树各有 1 种